public class LeetCode278 {
    public boolean isBadVersion(int version) {
        return version >= 9;
    }

    public int firstBadVersion(int n) {

        int index = n / 2;
        int left = 0;
        int rigth = n;

        while (index > 0 && index <= n) {

//            System.out.println("isBadVersion(index):" + isBadVersion(index));
            //如果是错误的版本的话
            if (isBadVersion(index)) {
                if (index == 1 || index == n) {
                    return index;
                }

                if (!isBadVersion(index - 1)) {
                    return index;
                } else {
                    rigth = index;
                }
            } else {//如果不是错误的版本的话
                left = index + 1;

            }
            index = left +  (rigth - left) / 2;

//            System.out.println("left:" + left + " right:" + rigth + " index:" + index);

        }

        return 1;
    }

    public int firstBadVersion2(int n) {

        int left = 1;
        int rigth = n;

        while (left < rigth){
            int mid = left + (rigth - left)/ 2;
            if (isBadVersion(mid)){
                rigth = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}
